package 丑数;

//题目描述
//把只包含质因子2、3和5的数称作丑数（Ugly Number）。
// 例如6、8都是丑数，但14不是，因为它包含质因子7。
// 习惯上我们把1当做是第一个丑数。
// 求按从小到大的顺序的第N个丑数。
public class Solution {
    //笨方法，遍历n之前的数组，对每个数依次一直除，2,3，5，看最后是否为1，是则是丑数，否则不是
    //重复计算了丑数，建立一个数组，存储已经验证过的丑数，新的丑数只要在原来的基础上×2,3,5即可
    public int GetUglyNumber_Solution(int index) {
        if (index <= 0)
            return 0;
        int[] uglynums = new int[index];
        uglynums[0] = 1;
        //定义指针
        int p2 = 0;
        int p3 = 0;
        int p5 = 0;
        for (int i = 1; i < index; i++) {
            uglynums[i] = Math.min(uglynums[p2] * 2, Math.min(uglynums[p3] * 3, uglynums[p5] * 5));
            if (uglynums[i] == uglynums[p2] * 2)//指针其实指的是，此索引所指前面的丑数乘2都小于当前数组最大的丑数，后面的大于最大的丑数
                p2++;//要继续向前推进，就要把指针++，然后取三个指针分别乘2,3,5三个数的最小值作为新的丑数。
            if (uglynums[i] == uglynums[p3] * 3)
                p3++;
            if (uglynums[i] == uglynums[p5] * 5)
                p5++;
        }
        return uglynums[index - 1];
    }
}
